package leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-12-24 15:00
 **/
public class LeetCode98 {

    //中序遍历(二叉搜索的中序遍历是升序的
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<>();
        long inorder = Long.MIN_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            root = stack.pop();
            if (root.val <= inorder) {
                return false;
            }

            inorder = root.val;
            root = root.right;
        }
        return true;
    }


    //递归
    /*public boolean isValidBST(TreeNode root) {
        //由于节点的值的范围是(Integer.MIN_VALUE,Integer.MAX_VALUE),所以需要使用Long的最小值和最大值来表示上下界
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long lower, long upper) {
        if (root == null) {
            return true;
        }

        //节点值小于等于下界或者大于等于上界返回false
        if (root.val <= lower || root.val >= upper) {
            return false;
        }
        //递归左子树和右子树
        return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val ,upper);

    }*/


}
